<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
<script>
// 多多最近在玩一种骨牌游戏，在一条直线上n个骨牌，骨牌只有高度没有宽度，第i个骨牌在位置xi，其高度为hi，
// 多多可以任意选择一些骨牌，将其按顺序向左或者向右放倒，向左放倒之后会占竭[xi-hi,xi]对，向右放倒后会占据[xi,xi+hi]。
// 要求放倒的骨牌不能触碰到其他之前已经放倒的骨牌或者站立的骨牌。问多多最多可以放倒多少个骨牌。
// 贪心算法，从左到右推骨牌，能往左倒就左倒（推倒骨牌数量加1并且不占用下一个骨牌的位置），其次是右倒（推倒骨牌数量加一，但是占用下一个骨牌的位置），最后就是不推（数量不变）。
// 因为我们是从左到右遍历骨牌，所以最后一个骨牌一定可以向右推倒。所以遍历从0到n-1的数组即可，最后推到骨牌数加一。
function maxFallenDominoes(n, dominos) {
  let fallen = 0; // 放倒的骨牌数量
  let lastFallen = -Infinity; // 上一个已放倒骨牌的位置

  for (let i = 0; i < n - 1; i ++) {
    const [pos, height] = dominos[i];
    const leftRange = pos - height;
    const rightRange = pos + height;

    if (leftRange > lastFallen) { // 可以向左放倒
      fallen++;
      lastFallen = pos;
    } else if (rightRange < dominos[i + 1][0]) { // 可以向右放倒
      fallen++;
      lastFallen = pos + height;
    } else { // 没法放倒
        lastFallen = pos;
    }
  }

  return fallen + 1;
}
const n = 5;
const dominos = [[2, 1], [4, 3], [5, 2], [7, 3], [10, 1]];
console.log(maxFallenDominoes(n, dominos)); // 输出：2
const n2 = 3;
const dominos2 = [[1, 1], [2, 1], [3, 1]];
console.log(maxFallenDominoes(n2, dominos2)); // 输出：2
const n3 = 3;
const dominos3 = [[1, 5], [2, 1], [4, 5]];
console.log(maxFallenDominoes(n3, dominos3)); // 输出：3
</script>
</body>
</html>